class TreeNode:
    def __init__(self, x=0):
        self.val = x
        self.left = None
        self.right = None


def is_complete_binary_tree(root: TreeNode):
    """
    判断是否是一颗完全二叉树：
    :param root:
    :return:
    """
    if not root:
        return True
    leaf = False
    queue = deque()
    queue.append(root)
    while queue:
        node = queue.popleft()
        l = node.left
        r = node.right
        if (leaf and (l or r)) or (r and not l):
            return False
        if l:
            queue.append(l)
        if r:
            queue.append(r)
        else:
            leaf = True
    return True


if __name__ == "__main__":
    head = TreeNode(6)
    head.left = TreeNode(3)
    head.left.left = TreeNode(1)
    head.left.left.right = TreeNode(2)
    head.left.right = TreeNode(4)
    head.left.right.right = TreeNode(5)
    head.right = TreeNode(9)
    head.right.left = TreeNode(8)
    head.right.left.left = TreeNode(7)
    head.right.right = TreeNode(10)
    print(is_complete_binary_tree(head))